package leetcode_800;

/**
 *@author 周杨
 *DominoAndTrominoTiling_790 多米诺骨牌的排列方式
 *describe:用动态规划 AC 65%
 *2018年10月22日 下午3:44:46
 */
public class DominoAndTrominoTiling_790 {
	
	
	//开始定义状态 规则是无论如何不超过本列 而且前面都是合法排列
	/*
	 * 0 |左侧满 
	 * 1 只有一侧
	 */
	public int numTilings1(int N) {
		int MOD=1000000007;
		long [][]dp=new long[N+1][2];//long决定了不会反向越界
        dp[0][0]=1;
        dp[1][0]=1;//初始化
        for(int i=2;i<=N;++i) {
        	dp[i][0]=(dp[i-2][0]//这个是横着铺两列
        			+dp[i-1][0]//这个是竖着铺一列
        			+dp[i-1][1]+MOD)%MOD;
        	dp[i][1]=(dp[i-2][0]*2+dp[i-1][1]+MOD)%MOD;
        }
        return (int) dp[N][0];
    }
}
